In real-time three dimensional (3D) graphical simulation, real-world objects may be modeled as a set of polygons. For example, a set of six polygons may be used to model a house: four rectangles model the sides of the house, one rectangle models the roof, another rectangle models the door. The presentation of the modeled objects depends on the vantage point being simulated. For example, from a vantage point directly in front of the house, two rectangles of the model are displayed, i.e. the rectangle for the front face of the house and the rectangle for the door. As the vantage point is moved further away, the size of the rectangles used to model house is decreased to simulate the house being further away.
The vantage point that is being simulated is herein referred to as the eye view. An eye view in a real-time 3D graphical system may change over time and in response to user input. For example, a change in direction of an airplane brought about by user manipulation of a joy stick in a flight simulator causes the eve view to change. As the time elapses and the simulated plane moves, corresponding changes to the eye view occur.
Modeling real-world objects with polygons involves a trade-off between the number of polygons used to model objects and system performance. The greater the number of polygons used present real-world objects, the greater the detail presented. However, a greater number of polygons increases system load, and decreases response time and refresh rates.
One approach for managing the tradeoff is the "level of detail switching" approach. Under the level of detail switching approach, when an object is further away it is modeled at a coarser level of detail with a lesser number of polygons. When the object is closer, it is modeled at a finer level of detail with a greater number of polygons. For example, to model the house from an eye view that is further away, the house is modeled at a first level of detail using the six rectangles mentioned previously. As the eye view moves closer, the house is modeled at a second level of detail finer than the first, using a greater number polygons, e.g. additional rectangles to model windows.
The level of detail switching works well for discrete objects that occupy a small amount of space relative to the environment being simulated (e.g. houses, airplanes, cars). However, the approach is problematic for large objects, such as terrain.
When simulating terrain, it is desirable to present the terrain as a large continuous surface, with greater detail in the foreground and less detail in the background. However, presenting the terrain as a single object all of which is at a particular level of detail may present sufficient detail in the foreground but too much in the background. Furthermore, simulating all the terrain at a level of detail that was a relatively large number of polygons may cause an undesirable load on the computer system. Consequently, techniques have been developed to model terrain as a group of adjacent objects which are displayed as varying levels of detail.
One such approach is the grid approach. In the grid approach, the terrain is broken up into tiles, with multiple levels of detail representations for each tile. The tiles that are closer to the eye view are presented at a finer level of detail (i.e. modeled with a greater number of polygons), and tiles further away are presented at a coaster level of detail.
To give the terrain a continuous appearance, the edges of polygons in one tile that lie along an edge shared with another tile must coincide with the edges of polygons in the other tile. More specifically, any vertex of a polygon in one tile that lies on the shared edge must coincide with a vertex of polygon in the other tile. When the vertices along a shared edge of two tiles coincide in the manner, the shared edge is said to be matched.
For example, in FIG. 2A; tile 202 (not all polygons of tile 202 are shown) and tile 208 shared edge 220. Five vertices 222, lie on tile edge 220. Each of vertices 222 is a vertex of at least one polygon in tile 202 and of at least one polygon in tile 208. Likewise, all vertices 222 on tile edge 220 are vertices of at least one polygon in tile 202 and in tile 210.
To help maintain a continuous appearance, a given shared edge of a tile must be matched by any neighbor tile sharing the given shared edge regardless of the level of details at which the two tiles are displayed. One approach to ensuring that shared edges between tiles displayed at different levels of detail match is the "uniform-border-vertex" approach. Under the uniform-border-vertex approach, the vertices lying along an edge of a given tile coincide to the vertices lying on the corresponding edges of the other tiles that are different level of detail representations of the given tile.
For example, in FIG. 2B, tile 210 is a finer level of detail representation of tile 208 (not all polygons of tile 208 are shown). The vertices 222 of polygons in tile 210 that lie on tile edge 220 coincide with the vertices of polygons in tile 208 that lie on tile edge 220.
A drawback to the uniform border vertex approach is that, for some levels of detail, areas near the edge of the tile appear to be at a different resolution than areas in the interior. Furthermore, the appearance of a different resolution between the edge regions and interior regions makes the borders between tiles more visible and causes the appearance of walls running throughout the simulated terrain.
It is clearly desirable to provide a method of representing terrain with tiles whose resolutions do not appear to differ at the edge regions. It is further desirable to provide a method which reduces the appearance of walls running throughout the terrain.